The present invention relates to computer software, and, more particularly, to stack tracebacks which provide the values held by one or more registers upon entry to each function in a call chain.
In order to reduce the frequency of relatively time-consuming accesses to main memory, compilers and programmers typically generate code using registers of a target processor for the storage of some or all function local variables. However, each function may call another function which, in turn, may modify the contents of one or more of the registers used for storing local variables of the calling function. Several solutions are possible for ensuring that the correct values of the calling function's local variables, as held in one or more registers, are preserved upon resumption of execution in the calling function after a return from the called function:
1) Before a function calls another function, the calling function could save, to main memory, the values of all registers currently storing local variables of the calling function. After the return from the called function, the calling function would restore the saved values into the registers. Typically, a region of reserved memory, known as a runtime stack, is used for storing the above register values. Before performing the above saving, a function allocates an area at the top of the runtime stack, sometimes referred to as a frame. A frame provides storage for various types of information pertaining to a particular invocation of a function. Each frame is deallocated from (popped off) the stack before returning from the function that created the frame.
The advantage of the above solution is that values of all local variables are self-contained in the frame of current invocation. Thus, external, runtime probes such as debuggers or exception handlers can easily find them. However, this solution is somewhat inefficient with respect to computation time and memory requirements because frequently a called function will not modify one or more of the registers that the calling function is using (and, thus, saving these registers in memory is unnecessary). Efficiency is a particular concern with modern processors having a large number of registers that could be used for local variable storage.
2) By convention, certain registers could be designated "non-volatile." It would be the responsibility of a called function to save, to a frame for the called function in the runtime stack, the value held by a non-volatile register upon entry to the called function if and before the called function modifies the register. The called function would also be responsible for restoring the value saved on the stack to the register before returning to the calling function.
The second solution is the approach taken by the System V Application Binary Interface (ABI) for the PowerPC. The specification for this interface is published by Sun Microsystems, Inc. of Mountain View, Calif. and, hereby, incorporated by reference for all purposes. This ABI specifies various conventions to ensure that any function compiled to run under the System V operating system on the PowerPC processor, can correctly interface with any other such function. One of the conventions specified by this ABI is that integer registers r14-r31 and floating-point registers f14-f31 are non-volatile.
In various contexts such as debugging and exception handling, it may be necessary to determine the value held by a particular non-volatile register upon entry to a particular function in a call chain. A call chain is a sequence of nested function calls occurring during program execution. For example, if a program's main routine calls function A and function A calls function B, then the call chain existing during execution within function B consists of: the main routine, followed by function A, followed by function B. Typically, the runtime stack has one frame for each invocation of each function in the current call chain (except, possibly, for the last function called), which stores information pertaining to the function. Under special circumstances, an existing frame may be reused or extended instead of creating a new one.
In the above contexts, it would be necessary to determine whether the value held by the particular non-volatile register upon entry to the particular function is still in the register at the time execution reaches a particular address inside the particular function. The particular address is the address of the call from the particular function to the next function in the call chain, or in the case of the last function in the call chain, the address where execution of the program stops before the debugger or exception handling software takes over. If the required value is not in the register, the required value must be retrieved from the function's stack frame.
For example, debuggers typically permit a user to specify a breakpoint at an arbitrary location within any function. Upon reaching a breakpoint, such debuggers may examine the frames on the stack and provide the user with the current call chain. In addition, users can typically request the value of a particular local variable at the time of the call to a particular function in the call chain. Compiler-produced data, accessible to the debugger, indicates the particular non-volatile register in which the particular local variable is stored at the time of the particular function call. Thus, it becomes necessary to determine the value of the particular non-volatile register upon entry to the particular called function.
For example, suppose a breakpoint at line 10 in function func2 is specified and that the breakpoint is reached after a call to function func2 from line 20 of a function func1 which has a local variable a. Suppose the debugger examines the appropriate compiler-produced data to determine that local variable a at line 20 of func1 is stored in non-volatile register 15. However, the value of register 15 might have been changed inside func2 by the time the breakpoint at line 10 of func 2 was reached. Thus, the debugger must be able to determine the location, at the time the breakpoint in func2 is reached, of the value held by register 15 upon entry to func2. This location will either be register 15 or func2's stack frame.
Exception handling for some modern programming languages represents another context where it may be necessary to determine the contents of non-volatile registers upon entry to functions in a calling chain. For example, consider a C++ program containing a function func1 that catches a particular type of exception (i.e., using a "catch" statement) and calls another function func2 that generates that type of exception (i.e., using a "throw" statement). When the exception is generated in func2, execution returns to func1 where the exception handling code inside the catch statement is executed. Upon the return to func1, the non-volatile registers must be restored to their values at the time of the call to func2. For example, one or more of the non-volatile registers may have held pointers to memory that must be deallocated by the exception handling code within func1's catch statement. Thus, the exception handler must be able to determine the respective location, at the time the exception is generated in func2, of the value held by each non-volatile register upon entry to func2. This location will either be the register or func2's stack frame.
Debuggers and exception handlers are only instances of a more generic class of utilities which perform stack tracebacks. A standalone lightweight stack traceback utility is often found useful for past mortem analysis of failed executables. Another example is a standalone performance collector/analyzer which also requires call-chain information.
As illustrated by the above discussion, there is a need for a general capability to determine the location, at the time execution reaches any particular address in any particular function in a call chain, of the value held by any non-volatile register upon entry to the particular function. Compiler-produced records (herein referred to as "tags") that form part of the compiled code, have been used to provide the required information regarding the location of the values held by non-volatile registers upon function entry. For example, a tag might indicate that, when the value stored by the program counter (hereinafter "PC value") is within a particular virtual address range of the program, the values held in various non-volatile registers at the time of entry to the function associated with the virtual address range are stored in the function's stack frame, at specific locations.
Two basic types of tags have been proposed, in-line and out-of-line. An in-line tag is stored adjacent to the first instruction to which it applies. Out-of-line tags are stored as a group in a "tag section" of the compiled entity, apart from the compiled instructions to which they apply. Thus, each out-of-line tag must generally store information indicating the virtual address range to which the tag applies.
In-line tags generally require a field identifying themselves as tags (to the debugger or exception handler) as opposed to machine instructions (between which they are stored). Furthermore, the compiler must generate branch instructions to cause the processor to skip over the tags. In-line tags require debuggers or exception handlers to have a working knowledge of the underlying instruction set, in order to be decoded. Out-of-line tags are largely insensitive to these details. In-line tags are inserted into instruction stream and hence increase code size, affect caching behavior and require larger working sets. Out-of-line tags have none of these restrictions and can even be stripped from the executable, if desired. Self-relative tag references can also be shared among processes that map shared libraries. For these reasons, out-of-line tags are favored.
Several complications in using out-of-line tags (hereinafter referred to simply as "tags") are introduced in environments supporting shared objects. In such environments, a program executable may consist of a primary load object and one or more shared objects which are loaded dynamically into the program's virtual address space during execution. Each object has its own tag section containing tags that apply to the compiled instructions stored within the object. A mechanism is required to enable the debugger or exception handler to determine which tag section applies to any given virtual address (also referred to herein as a PC value) in the program.
In addition, a shared object may, by definition, be loaded into the address spaces of many different programs (or even into the address space of one program at different times during execution), at different virtual addresses. One way of implementing tags involves explicitly storing in the tags the respective virtual address ranges to which the tags apply. Such tags would have to be modified each time the shared object in which they reside is loaded at a different virtual address. Thus, it would be highly desirable to have a mechanism whereby the contents of the tags stored in a shared object could remain constant regardless of the virtual addresses of the instructions to which they apply.